package com.leetcode.algorithm.y19.m03;

import java.util.LinkedList;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)222. 完全二叉树的节点个数
 * (done)654. 最大二叉树
 * @author: jie.deng
 * @time: 2019年3月8日 下午10:39:57
 */
public class MySolution0308 {
	
	/**
	 * 222. 完全二叉树的节点个数
	 * 
     * 给出一个完全二叉树，求出该树的节点个数。
     * 
     * 说明：
     * 
     * 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
     * 
     * 示例:
     * 
     * 输入: 
     *     1
     *    / \
     *   2   3
     *  / \  /
     * 4  5 6
     * 
     * 输出: 6
	 * @param root
	 * @return
	 */
	public int countNodes(TreeNode root) {
		// 常规解法:广度优先遍历,数结点个数
		int cnt = 0;
		if (root == null) {
			return 0;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			cnt++;
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		return cnt;
	}
    
    /**
     * 654. 最大二叉树
     * 
     * 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
     * 
     * 二叉树的根是数组中的最大元素。
     * 左子树是通过数组中最大值左边部分构造出的最大二叉树。
     * 右子树是通过数组中最大值右边部分构造出的最大二叉树。
     * 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
     * 
     * Example 1:
     * 
     * 输入: [3,2,1,6,0,5]
     * 输入: 返回下面这棵树的根节点：
     * 
     *       6
     *     /   \
     *    3     5
     *     \    / 
     *      2  0   
     *        \
     *         1
     * 注意:
     * 
     * 给定的数组的大小在 [1, 1000] 之间。
     * @param nums
     * @return
     */
	public TreeNode constructMaximumBinaryTree(int[] nums) {
		return constructMaximumBinaryTree(nums, 0, nums.length - 1);
	}

	private TreeNode constructMaximumBinaryTree(int[] nums, int fromIdx, int toIdx) {
		if (fromIdx > toIdx) {
			return null;
		} else if (fromIdx == toIdx) {
			return new TreeNode(nums[fromIdx]);
		}
		int max = nums[fromIdx];
		int maxIdx = fromIdx;
		for (int i = fromIdx + 1; i <= toIdx; i++) {
			if (nums[i] > max) {
				max = nums[i];
				maxIdx = i;
			}
		}
		TreeNode root = new TreeNode(max);
		root.left = constructMaximumBinaryTree(nums, fromIdx, maxIdx - 1);
		root.right = constructMaximumBinaryTree(nums, maxIdx + 1, toIdx);
		return root;
	}
}
